package Leetcode.动态规划;

import java.util.Arrays;

/**
 * @Author: kirito
 * @Date: 2024/9/23 16:34
 * @Description:
 * 给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和一个整数 k 。
 *
 * 你可以执行下述 递增 运算 任意 次（可以是 0 次）：
 *
 * 从范围 [0, n - 1] 中选择一个下标 i ，并将 nums[i] 的值加 1 。
 * 如果数组中任何长度 大于或等于 3 的子数组，其 最大 元素都大于或等于 k ，则认为数组是一个 美丽数组 。
 *
 * 以整数形式返回使数组变为 美丽数组 需要执行的 最小 递增运算数。
 *
 * 子数组是数组中的一个连续 非空 元素序列。
 *
 * 示例 1：
 *
 * 输入：nums = [2,3,0,0,2], k = 4
 * 输出：3
 * 解释：可以执行下述递增运算，使 nums 变为美丽数组：
 * 选择下标 i = 1 ，并且将 nums[1] 的值加 1 -> [2,4,0,0,2] 。
 * 选择下标 i = 4 ，并且将 nums[4] 的值加 1 -> [2,4,0,0,3] 。
 * 选择下标 i = 4 ，并且将 nums[4] 的值加 1 -> [2,4,0,0,4] 。
 * 长度大于或等于 3 的子数组为 [2,4,0], [4,0,0], [0,0,4], [2,4,0,0], [4,0,0,4], [2,4,0,0,4] 。
 * 在所有子数组中，最大元素都等于 k = 4 ，所以 nums 现在是美丽数组。
 * 可以证明无法用少于 3 次递增运算使 nums 变为美丽数组。
 * 因此，答案为 3 。
 * 示例 2：
 *
 * 输入：nums = [0,1,3,3], k = 5
 * 输出：2
 * 解释：可以执行下述递增运算，使 nums 变为美丽数组：
 * 选择下标 i = 2 ，并且将 nums[2] 的值加 1 -> [0,1,4,3] 。
 * 选择下标 i = 2 ，并且将 nums[2] 的值加 1 -> [0,1,5,3] 。
 * 长度大于或等于 3 的子数组为 [0,1,5]、[1,5,3]、[0,1,5,3] 。
 * 在所有子数组中，最大元素都等于 k = 5 ，所以 nums 现在是美丽数组。
 * 可以证明无法用少于 2 次递增运算使 nums 变为美丽数组。
 * 因此，答案为 2 。
 * 示例 3：
 *
 * 输入：nums = [1,1,2], k = 1
 * 输出：0
 * 解释：在这个示例中，只有一个长度大于或等于 3 的子数组 [1,1,2] 。
 * 其最大元素 2 已经大于 k = 1 ，所以无需执行任何增量运算。
 * 因此，答案为 0 。
 */

public class 使数组变美的最小增量运算数 {
    public long minIncrementOperations(int[] nums, int k) {
        int n = nums.length;
        long[][] memo = new long[n][3];
        for (long[] arr : memo) {
            Arrays.fill(arr, -1); //-1表示没有计算过
        }
        return dfs(n - 1, 0, memo, nums, k);
    }

    /**
     * https://www.bilibili.com/video/BV1tw411q7VZ/?vd_source=bb13dc2c93abb249d3580e11536700c1
     * @param i  表示当前位置
     * @param j  表示右边有几个没有增大的数
     *           dfs(i,j) 表示在该状态下对于前 i 个数的最小递增运算数。
     *
     * 任何长度大于或等于3的子数组
     * 任何长度等于3的子数组
     * 包含至少一个>=k的数
     * 选一个子序列，子序列的所有元素都需要变成>=k的数
     * 子序列的相邻元素，不能间隔太大，子序列相邻元素的下标差<=3的
     * DP选或不选枚举选哪个
     * 如何消除“后效性”？
     * 定义dfs(i，j)表示现在要处理Nums[0]到Nums[i]这段子数组
     * 并且Nums[i]右边有j个没有变大的数
     * 选：dfs(i，j)=dfs(i-1，0)+max(k-数字[i]，0)
     * 不选(当j<2的时候)：DFS(i，j)=DFS(i-1，j+1)
     *
     *  灵神！！！
     */
    private long dfs(int i, int j, long[][] memo, int[] nums, int k) {
        if (i < 0) {
            return 0;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        long res = dfs(i - 1, 0, memo, nums, k) + Math.max(k - nums[i], 0); // nums[i]增大
        if (j < 2) {
            res = Math.min(res, dfs(i - 1, j + 1, memo, nums, k)); //nums[i] 不增大
        }
        memo[i][j] = res;
        return res;
    }
}
